Graph Minor

释义 Definition

图小子（graph minor）：在图论中，若一个图 H 可以通过对另一个图 G 进行若干次操作得到——删除顶点、删除边、以及收缩边（edge contraction）——则称 H 是 G 的一个 minor（小子）。这是结构图论与算法图论中的核心概念。（注：在某些语境下也会区分 minor、subgraph、topological minor 等相关概念。）

发音 Pronunciation (IPA)

/ˈɡræf ˈmaɪnər/

例句 Examples

A triangle is a graph minor of many larger graphs.
三角形是许多更大图的一个图小子。

The Graph Minor Theorem implies that any minor-closed family of graphs can be characterized by a finite set of excluded minors.
图小子定理表明：任何对取小子封闭的图族，都可以用有限个“被排除的小子”来刻画。

词源 Etymology

graph 源自希腊语 graphein（“书写、绘画”），引申为“图形/图”。minor 源自拉丁语 minor（“更小的”）。在图论里，minor 被专门化为“通过删除与收缩得到的更小结构”，强调的是“结构上的更简化版本”，而不只是顶点数更少。

相关词 Related Words

• Contraction
• Subgraph
• Topological Minor
• Minor-Closed
• Excluded Minor
• Treewidth
• Kuratowski Theorem
• Planar Graph

文学与经典出处 Literary Works

• Robertson & Seymour, Graph Minors（系列论文，发表于 Journal of Combinatorial Theory, Series B）：奠定并发展了图小子理论框架与图小子定理。
• Reinhard Diestel, Graph Theory：以教材形式系统介绍 minor、树宽（treewidth）、排除小子等核心内容。
• Douglas B. West, Introduction to Graph Theory：在入门教材中讲解 minor 与平面图、Kuratowski 定理等的联系。
• Neil Robertson & Paul D. Seymour, 相关综述与后续著作：在算法与结构图论中广泛引用 graph minor 概念（如固定参数算法、结构分解等）。